package main

import "fmt"

func main() {
	node := Constructor(2)
	node.Put(1, 1)
	get := node.Get(1)
	fmt.Println(get)
}

type LRUCache struct {
	head Node
	tail Node
	hmap map[int]Node
}
type Node struct {
	key   int
	value int
	next  *Node
	prev  *Node
}

func Constructor(capacity int) LRUCache {
	head := Node{
		-1, -2, nil, nil,
	}
	tail := Node{
		-2, -1, nil, nil,
	}
	head.next = &tail
	tail.prev = &head
	hmap := make(map[int]Node, 0)
	return LRUCache{
		head, tail, hmap,
	}
}
func insertNode(prev, node *Node) {
	next := prev.next
	node.prev = prev
	node.next = next
	prev.next = node
	next.prev = node
}
func deleteNode(node *Node) {
	next := node.next
	prev := node.prev
	node.next = nil
	node.prev = nil
	next.prev = prev
	prev.next = next
}
func (this *LRUCache) Get(key int) int {
	if v, ok := this.hmap[key]; ok {
		deleteNode(&v)

		insertNode(&(this.head), &v)
		return v.value
	}
	return -1
}
func (this *LRUCache) Put(key int, value int) {
	if v, ok := this.hmap[key]; ok {
		v.value = value
		deleteNode(&v)
		insertNode(&(this.head), &v)
		return
	}
	node := Node{
		key, value, nil, nil,
	}
	this.hmap[key] = node
	insertNode(&(this.head), &node)
}
